import java.util.*;
public class test {
    //leetcode 36.有效的数独
    class Solution {
        // 行
        public boolean[][] row;
        // 列
        public boolean[][] col;
        // 块
        public boolean[][][] count;
        public char[][] board;
        public boolean flg = true;

        public boolean isValidSudoku(char[][] board) {
            row = new boolean[9][9];
            col = new boolean[9][9];
            count = new boolean[3][3][9];
            this.board = board;
            // 传入行和列
            dfs(0,0);
            return flg;
        }

        public void dfs(int r,int c) {
            if(flg == false){
                return;
            }
            if(r == 9){
                return;
            }
            if(c == 9){
                dfs(r + 1,0);
                //避免执行后续代码
                return;
            }
            if(board[r][c] == '.'){
                dfs(r,c + 1);
                //避免执行后续代码
                return;
            }
            int num = board[r][c] - '1';
            if(row[r][num] || col[c][num] || count[r / 3][c / 3][num]){
                flg = false;
                return;
            }else {
                row[r][num] = true;
                col[c][num] = true;
                count[r / 3][c / 3][num] = true;
                dfs(r,c + 1);
                row[r][num] = false;
                col[c][num] = false;
                count[r / 3][c / 3][num] = false;
            }
        }
    }
    //leetcode 37.解数独
    class Solution {
        // 行
        public boolean[][] row;
        // 列
        public boolean[][] col;
        // 块
        public boolean[][][] count;

        public void solveSudoku(char[][] board) {
            row = new boolean[9][10];
            col = new boolean[9][10];
            count = new boolean[3][3][10];
            //初始化row,col,count
            for(int i = 0;i < 9;i++){
                for(int j = 0;j < 9;j++){
                    if(board[i][j] != '.'){
                        int n = board[i][j] - '0';
                        row[i][n] = true;
                        col[j][n] = true;
                        count[i / 3][j / 3][n] = true;
                    }
                }
            }
            // 传入行和列
            dfs(board);
        }

        public boolean dfs(char[][] nums) {
            for(int i = 0;i < 9;i++){
                for(int j = 0;j < 9;j++){
                    //查找'.',并且对其进行查找修改
                    if(nums[i][j] == '.'){
                        for(int num = 1;num < 10;num++){
                            //为true则代表该数字正好合法,可以尝试填入
                            if(!row[i][num] && !col[j][num] && !count[i / 3][j / 3][num]){
                                row[i][num] = true;
                                col[j][num] = true;
                                count[i / 3][j / 3][num] = true;
                                nums[i][j] = (char)(num + '0');
                                //如果此时为true,则继续进行查找
                                if(dfs(nums) == true){
                                    return true;
                                }
                                //恢复现场
                                row[i][num] = false;
                                col[j][num] = false;
                                count[i / 3][j / 3][num] = false;
                                nums[i][j] = '.';

                            }
                        }
                        //如果遍历到此,则代表没有成功填数,则返回false
                        return false;
                    }
                }
            }
            //如果两层遍历结束,则代表此表填完,返回true
            return true;
        }
    }
}
